class Solution {
    /*
        思路1：动态规划
            每次从较短的字符串开始转移到较长的字符串
            所以先枚举终点
        时间/空间：O(N^2)，
    */
    public String longestPalindrome(String s) {
        String ans = "";
        int len = s.length();
        boolean[][] d = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                char ch1 = s.charAt(i), ch2 = s.charAt(j);
                if (i == j)
                    d[i][j] = true;
                else if (j - i == 1)
                    d[i][j] = (ch1 == ch2);
                else
                    d[i][j] = d[i + 1][j - 1] && (ch1 == ch2);
                if(d[i][j] == true && j-i+1 > ans.length()){
                    ans = s.substring(i,j+1);
                }
            }
        }
        return ans;
    }
}
class Solution {
    /*
        思路2：中心扩展
        我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，
    */
    public String longestPalindrome(String s) {
        String ans = "";
        // 枚举起点
        for (int i = 0, len=s.length(); i < len; i++) {
            int len1 = check(s,i,i);
            int len2 = check(s,i,i+1);
            // System.out.println("i="+i+", len1:"+len1+" ,len2="+len2);
            if(len1>ans.length()){
                ans = s.substring(i-len1/2,i+len1/2+1);
            }
            if (len2>ans.length()){
                ans = s.substring(i+1-len2/2,i+len2/2+1);
            }
        }
        return ans;
    }
    public int check(String s,int left,int right){
        int len = s.length();
        while(left >=0 && right < len && s.charAt(left)==s.charAt(right)){
            left --;
            right++;
        }
        return right-left-1;
    }
}